﻿using System;

namespace UFrame.Tool
{
    public class SearchTool
    {
        /// <summary>
        /// LCS算法
        /// </summary>
        /// <param name="s1"></param>
        /// <param name="s2"></param>
        /// <returns></returns>
        public static string LCS(string s1, string s2)
        {
            if (s1 == s2)
                return s1;
            else if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
                return null;

            var d = new int[s1.Length, s2.Length];

            var index = 0;
            var length = 0;

            for (int i = 0; i < s1.Length; i++)
            {
                for (int j = 0; j < s2.Length; j++)
                {
// 左上角值
                    var n = i - 1 >= 0 && j - 1 >= 0 ? d[i - 1, j - 1] : 0;

// 当前节点值 = "1 + 左上角值" : "0"
                    d[i, j] = s1[i] == s2[j] ? 1 + n : 0;

// 如果是最大值，则记录该值和行号
                    if (d[i, j] > length)
                    {
                        length = d[i, j];
                        index = i;
                    }
                }
            }

            return s1.Substring(index - length + 1, length);
        }

        //字符串模糊匹配算法
        public static int LevenshteinDistance(string s1, string s2)
        {
            if (s1 == s2)
                return 0;
            else if (String.IsNullOrEmpty(s1))
                return s2.Length;
            else if (String.IsNullOrEmpty(s2))
                return s1.Length;

            var m = s1.Length + 1;
            var n = s2.Length + 1;
            var d = new int[m, n];

// Step1
            for (var i = 0; i < m; i++)
            {
                d[i, 0] = i;
            }

// Step2
            for (var j = 0; j < n; j++)
            {
                d[0, j] = j;
            }

// Step3
            for (var i = 1; i < m; i++)
            {
                for (var j = 1; j < n; j++)
                {
                    var cost = s1[i - 1] == s2[j - 1] ? 0 : 1;

                    var deletion = d[i - 1, j] + 1;
                    var insertion = d[i, j - 1] + 1;
                    var substitution = d[i - 1, j - 1] + cost;

                    d[i, j] = Math.Min(Math.Min(deletion, insertion), substitution);
                }
            }

            return d[m - 1, n - 1];
        }

    }
}